home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / access / nbtree / README < prev   
Encoding:
Text File  |  1992-08-27  |  3.3 KB  |  69 lines
  1. $Header: /private/postgres/src/access/nbtree/RCS/README,v 1.5 1991/07/03 19:48:20 mao Exp $
  2.  
  3. This directory contains a correct implementation of Lehman and Yao's
  4. btree management algorithm that supports concurrent access for Postgres.
  5. We have made the following changes in order to incorporate their algorithm
  6. into Postgres:
  7.  
  8.     +  The requirement that all btree keys be unique is too onerous,
  9.        but the algorithm won't work correctly without it.  As a result,
  10.        this implementation adds an OID (guaranteed to be unique) to
  11.        every key in the index.  This guarantees uniqueness within a set
  12.        of duplicates.  Space overhead is four bytes.
  13.  
  14.        For this reason, when we're passed an index tuple to store by the
  15.        common access method code, we allocate a larger one and copy the
  16.        supplied tuple into it.  No Postgres code outside of the btree
  17.        access method knows about this xid or sequence number.
  18.  
  19.     +  Lehman and Yao don't require read locks, but assume that in-
  20.        memory copies of tree nodes are unshared.  Postgres shares
  21.        in-memory buffers among backends.  As a result, we do page-
  22.        level read locking on btree nodes in order to guarantee that
  23.        no record is modified while we are examining it.  This reduces
  24.        concurrency but guaranteees correct behavior.
  25.  
  26.     +  Read locks on a page are held for as long as a scan has a pointer
  27.        to the page.  However, locks are always surrendered before the
  28.        sibling page lock is acquired (for readers), so we remain deadlock-
  29.        free.  I will do a formal proof if I get bored anytime soon.
  30.  
  31. In addition, the following things are handy to know:
  32.  
  33.     +  Page zero of every btree is a meta-data page.  This page stores
  34.        the location of the root page, a pointer to a list of free
  35.        pages, and other stuff that's handy to know.
  36.  
  37.     +  This algorithm doesn't really work, since it requires ordered
  38.        writes, and UNIX doesn't support ordered writes.
  39.  
  40.     +  There's one other case where we may screw up in this
  41.        implementation.  When we start a scan, we descend the tree
  42.        to the key nearest the one in the qual, and once we get there,
  43.        position ourselves correctly for the qual type (eg, <, >=, etc).
  44.        If we happen to step off a page, decide we want to get back to
  45.        it, and fetch the page again, and if some bad person has split
  46.        the page and moved the last tuple we saw off of it, then the
  47.        code complains about botched concurrency in an elog(WARN, ...)
  48.        and gives up the ghost.  This is the ONLY violation of Lehman
  49.        and Yao's guarantee of correct behavior that I am aware of in
  50.        this code.
  51.  
  52. Notes to operator class implementors:
  53.  
  54.     With this implementation, we require the user to supply us with
  55.     a procedure for pg_amproc.  This procedure should take two keys
  56.     A and B and return < 0, 0, or > 0 if A < B, A = B, or A > B,
  57.     respectively.  See the contents of that relation for the btree
  58.     access method for some samples.
  59.  
  60. Notes to mao for implementation document:
  61.  
  62.     On deletions, we need to adjust the position of active scans on
  63.     the index.  The code in nbtscan.c handles this.  We don't need to
  64.     do this for splits because of the way splits are handled; if they
  65.     happen behind us, we'll automatically go to the next page, and if
  66.     they happen in front of us, we're not affected by them.  For
  67.     insertions, if we inserted a tuple behind the current scan location
  68.     on the current scan page, we move one space ahead.
  69.